/*
题目：回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
时间复杂度：O(n)      空间复杂度：O(1)
 */
public class IsPalindromeLink {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //先让slow到达中间节点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //反转后半部分
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //再分别从头，从尾开始对比
        fast = slow;//分别置为头和尾巴
        slow = head;
        while (fast != slow) { //没有相遇
            if (fast.val != slow.val) {
                return false;
            }
            if (slow.next == fast) {
                return true;
            }
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }
}
